COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\beginSection{Determining the Class Precedence List}
C00015 ENDMK
C⊗;
\beginSection{Determining the Class Precedence List}

The {\bf defclass} form for a class provides a total ordering on that
class and its direct superclasses.  This ordering is called the {\bit
local precedence order\/}.  It is an ordered list of the class and its
direct superclasses. A class precedes its direct superclasses, and a
direct superclass precedes all other direct superclasses specified to
its right in the superclasses list of the {\bf defclass} form.  For
every class $C$ we define $$R\sub C=\{(C,C\sub 1),(C\sub 1,C\sub
2),\ldots,(C\sub {n-1},C\sub n)\}$$ where $C\sub 1,\ldots,C\sub n$ are
the direct superclasses of $C$ in the order in which they are mentioned in the
{\bf defclass} form. These ordered pairs generate the total ordering on
the class $C$ and its direct superclasses.

Let $S\sub C$ be the set of $C$ and its superclasses. Let $R$ be
$$R=\bigcup\sub{c\in {S\sub C}}R\sub c$$

$R$ may or may not generate a partial ordering, depending on whether the
$R\sub c$, $c\in S\sub C$, are consistent; we assume they are consistent
and that $R$ generates a partial ordering. When the $R\sub c$ are not
consistent we say that $R$ is inconsistent.
This partial ordering is generated 
by taking the
the transitive closure
of the set $R\cup \{(c,c) \vert c\in {S\sub C}\}$.
When $(C\sub 1,C\sub 2)\in R$, we say that $C\sub 1$ {\bit
precedes} $C\sub 2$.

To compute the class precedence list at~$C$, we topologically sort the
elements of $S\sub C$ with respect to the partial ordering generated
by $R$.  When the topological sort must select a class from a set of
two or more classes, none of which are preceded by other classes with
respect to~$R$, the class selected is chosen deterministically, as
described below.

We require that an implementation of \CLOS\ signal an error if 
$R$ is inconsistent, that is, if the class precedence list cannot be
computed.

\beginsubSection{Topological Sorting}

Topological sorting proceeds by finding a class $C$ in~$S\sub C$
such that no other class precedes that element according to the
elements in~$R$.  $C$ is placed first in the result.  We remove $C$ from
$S\sub C$, and we remove all pairs of the form $(C,D)$,
$D\in S\sub C$, from $R$. We repeat the process, adding
classes with no predecessors at the end of the result.  We stop when
no element can be found that has no predecessor.

If $S\sub C$ is not empty and the process has stopped, the
set $R$ is inconsistent: if every class in the finite set of classes
is preceded by another, then $R$ contains a loop, and there
are two classes, $C\sub 1$ and $C\sub 2$, such that $C\sub 1$ precedes
$C\sub 2$ and $C\sub 2$ precedes $C\sub 1$.

\eject
Sometimes there are several classes from $S\sub C$ with no
predecessors.  In this case we select the one that has a direct
subclass rightmost in the class precedence list computed so far.
Because a direct superclass precedes all other direct superclasses to
its right, there can be only one such candidate class. If there are no
such candidate classes, $R$ does not generate a partial ordering---the
$R\sub c$, $c\in S\sub C$, are inconsistent.

In more precise terms, let $\{N\sub 1,\ldots,N\sub m\}$, $2\leq m$, be
the classes from $S\sub C$ with no predecessors.  Let $(C\sub
1\ldots C\sub n)$, $1\leq n$, be the class precedence list
constructed so far.  $C\sub 1$ is the most specific class and $C\sub
n$ is the least specific.  Let $1\leq j\leq n$ be the largest number
such that $\exists \thinspace i$ where $1\leq i\leq m$ and $N\sub i$
is a direct superclass of $C\sub j$; $N\sub i$ is placed next.

The effect of this rule for selecting from a set of classes with no
predecessors is that simple superclass chains and relatively separated
subgraphs are kept together in the class precedence list. For example,
let $T\sub 1$ and $T\sub 2$ be subgraphs whose only element in common is
the class {\bf t}; let $C\sub 1$ be the bottom of $T\sub 1$; and let
$C\sub 2$ be the bottom of $T\sub 2$. Suppose $C$ is a class whose direct
superclasses are $C\sub 1$ and $C\sub 2$ in that order, then the class
precedence list for $C$ will start with $C$ and will be followed by all
classes in $T\sub 1$; after all the classes of $T\sub 1$ will be all
classes in $T\sub 2$.

\endsubSection%{Topological Sorting}

\beginsubSection{Examples}

Here is an example of determining a class precedence list.  The classes
are defined:

\screen!

(defclass pie (apple cinnamon) ())

(defclass apple (fruit) ())

(defclass cinnamon (spice) ())

(defclass fruit (food) ())

(defclass spice (food) ())

(defclass food () ())
\endscreen!

The set $S$~$=$ $\{${\tt pie, apple, cinnamon, fruit, spice, food, t}$\}$. The
set $R$~$=$ $\{${\tt (pie, apple),
(apple, cinnamon), (apple, fruit), (cinnamon, spice),
(fruit, food), (spice, food), (food t)}$\}$.

The class {\tt pie} is not preceded by anything, so it comes first;
the result so far is {\tt (pie)}.  We remove {\tt pie} from $S$ and
pairs mentioning {\tt pie} from $R$ and get $S$~$=$ $\{${\tt
apple, cinnamon, fruit, spice, food, t}$\}$ and $R$~$=$ $\{${\tt
(apple, cinnamon), (apple, fruit), (cinnamon, spice),
(fruit, food), (spice, food), (food t)}$\}$.

\eject
The class {\tt apple} is not preceded by anything, so it is next; the
result is {\tt (pie apple)}. Removing {\tt apple} and the relevant
pairs we get $S$~$=$ $\{${\tt cinnamon, fruit, spice, food, t}$\}$ and
$R$~$=$ $\{${\tt (cinnamon, spice), (fruit, food),
(spice, food), (food t)}$\}$.

The classes {\tt cinnamon} and {\tt fruit} are not preceded by
anything, so we look at which of these two has a direct subclass
rightmost in the class precedence list computed so far.  The class
{\tt apple} is a direct subclass of {\tt fruit} and is rightmost in
the precedence list.  Therefore, we select {\tt fruit} next, and the
result so far is {\tt (pie apple fruit)}.  $S$~$=$ $\{${\tt cinnamon,
spice, food, t}$\}$; $R$~$=$ $\{${\tt (cinnamon, spice), (spice,
food), (food t)}$\}$.

The class {\tt cinnamon} is next, giving the result so far as {\tt (pie apple
fruit cinnamon)}.  $S$~$=$ $\{${\tt spice, food, t}$\}$; $R$~$=$
$\{${\tt (spice, food), (food t)}$\}$.

The classes {\tt spice}, {\tt food}, and {\tt t} are added in that
order, and the class precedence list is {\tt (pie apple fruit cinnamon
spice food t)}.

It is possible to write a set of class definitions that cannot be 
ordered.   For example: 

\screen!

(defclass new-class (fruit apple) ())

(defclass apple (fruit) ())
\endscreen!

The class {\tt fruit} must precede {\tt apple} because the local
ordering of superclasses is preserved.  The class {\tt apple} must
precede {\tt fruit} because a class always precedes its own
superclasses.  When this situation occurs, an error is signaled when
the system tries to compute the class precedence list.

Note the following example, which appears at first glance to be a
conflicting set of definitions: 

\screen!

(defclass pie (apple cinnamon) ())

(defclass pastry (cinnamon apple) ())

(defclass apple () ())

(defclass cinnamon () ())
\endscreen!

The class precedence list for {\tt pie} is  {\tt (pie apple cinnamon t)}.

The class precedence list for {\tt pastry} is  {\tt (pastry cinnamon apple t)}.

There is no problem with the fact that {\tt apple} precedes {\tt
cinnamon} in the ordering of the superclasses of {\tt pie} but does not in the
ordering for {\tt pastry}.  However, it is not possible to build a new class
that has both {\tt pie} and {\tt pastry} as superclasses.

\endsubSection%{Examples}

\endSection%{Determining the Class Precedence List}